// 版权2019 etcd作者
// 
// 根据Apache许可证2.0版（以下简称“许可证”）获得许可；
// 除非遵守许可证，否则不得使用此文件。
// 您可以通过
// 
// www.apache.org/licenses/LICENSE-2.0 
// 
// 除非适用法律要求或书面同意，否则根据许可证分发的软件
// 按“原样”分发，
// 无任何明示或暗示的保证或条件。
// 请参阅许可证，了解管理许可的特定语言和
// 许可证下的限制。

package tracker

import (
	"fmt"
	"sort"
	"strings"
)

// 在领导者看来，进步代表追随者的进步。领导者
// 维护所有追随者的进度，并根据其进度向追随者
// 发送条目。
// 
// NB（tbg）：进步基本上是一个状态机，其转换大部分是
// /散布在`*筏上。木筏`。此外，某些字段仅在
// 特定状态下使用。所有这些都不理想。
type Progress struct {
	Match, Next uint64
	// 状态定义领导者应如何与追随者互动。
	// 
	// 在StateProbe中，leader每个心跳间隔最多发送一条复制消息
	// 。它还探讨了追随者的实际进展。
	// 
	// 处于状态复制时，leader乐观地将next 
	// 增加到发送复制消息后发送的最新条目。这是
	// 用于将日志项快速复制到跟随者的优化状态。
	// 
	// 在状态快照中，leader应该在之前发送快照
	// 并停止发送任何复制消息。
	State StateType

	// 状态快照中使用PendingSnapshot。
	// 如果存在挂起的快照，则将挂起的快照设置为快照的
	// 索引。如果设置了pendingSnapshot，则
	// 的复制过程将暂停。raft将不会重新发送快照，直到报告挂起的
	// 失败。
	PendingSnapshot uint64

	// 如果进度最近处于活动状态，则RecentActive为真。从相应的跟随者处接收任何消息
	// 表明进度处于活动状态。
	// 选择超时后，RecentActive可以重置为false。
	// 
	// TODO（待定）：领导者应始终将此设置为真。
	RecentActive bool

	// 当此跟随者处于StateProbe时，使用ProbeSent。当ProbeSent为
	// true时，raft应暂停向该对等方发送复制消息，直到重置
	// ProbeSent。请参阅probeaked（）和IsPaused（）。
	ProbeSent bool

	// inflight是一个滑动窗口，用于显示机上消息。
	// 每条机上消息都包含一个或多个日志项。
	// raft配置中将每条消息的最大条目数定义为MaxSizePerMsg。
	// 因此飞行中有效地限制了飞行中消息的数量
	// 以及每个进度可以使用的带宽。
	// 航班已满时，不应再发送消息。
	// 当领导发出消息时，最后一个
	// 条目的索引应添加到行内。索引必须按顺序添加到飞行中。
	// 当领导收到回复时，应通过调用inflight释放先前的inflight。最后一个
	// 接收条目的索引为FreeLE。
	Inflights *Inflights

	// IsLearner如果为学习者跟踪此进度，则为真。
	IsLearner bool
}

// ResetState将进度移动到指定状态，重置ProbeSent、
// PendingSnapshot和Inflight。
func (pr *Progress) ResetState(state StateType) {
	pr.ProbeSent = false
	pr.PendingSnapshot = 0
	pr.State = state
	pr.Inflights.reset()
}

func max(a, b uint64) uint64 {
	if a > b {
		return a
	}
	return b
}

func min(a, b uint64) uint64 {
	if a > b {
		return b
	}
	return a
}

// 当此对等方接受追加时，调用probeaked。它重置
// ProbeSent，以表示应发送附加消息，而不会进一步延迟
// 。
func (pr *Progress) ProbeAcked() {
	pr.ProbeSent = false
}

// BecomeProbe转换为StateProbe。接下来重置为匹配+1或
// 可选，如果更大，则为挂起快照的索引。
func (pr *Progress) BecomeProbe() {
	// 如果原始状态为StateSnapshot，progress知道
	// 挂起的快照已成功发送到此对等方，则
	// 从pendingSnapshot+1进行探测。
	if pr.State == StateSnapshot {
		pendingSnapshot := pr.PendingSnapshot
		pr.ResetState(StateProbe)
		pr.Next = max(pr.Match+1, pendingSnapshot+1)
	} else {
		pr.ResetState(StateProbe)
		pr.Next = pr.Match + 1
	}
}

// 将转换简化为StateReplicate，在匹配+1的旁边重置。
func (pr *Progress) BecomeReplicate() {
	pr.ResetState(StateReplicate)
	pr.Next = pr.Match + 1
}

// BecomeSnapshot使用指定的挂起
// 快照索引。
func (pr *Progress) BecomeSnapshot(snapshoti uint64) {
	pr.ResetState(StateSnapshot)
	pr.PendingSnapshot = snapshoti
}

// 尝试修改Match字段和Next宇段，用来标识对应节点Entry记录复制的情况。
// Leader节点除了在向自身raftLog中追加记录时（即appendEntry（）方法）会调用该方法，
// 当Leader节点收到Follower节点的MsgAppResp消息（即MsgApp消息的响应消息〉时，
// 也会调用该方法尝试修改Follower节点对应的Progress实例。
func (pr *Progress) MaybeUpdate(n uint64) bool {
	var updated bool
	if pr.Match < n {
		pr.Match = n	// n之前的成功发送所有Entry记录已经写入对应节点的raftLog中
		updated = true
		// 下面将Progress.ProbeSent设立为false，表示Leader节点可以继续向对应Follower节点发送MsgApp消息（~f复制Entry记录）
		pr.ProbeAcked()
	}
	// 移动Next字段，下次妥复制的Entry记录从Next开始
	pr.Next = max(pr.Next, n+1)
	return updated
}

// 一直追加到并包括索引n的优化更新信号
// 正在运行中。因此，Next增加到n+1。
func (pr *Progress) OptimisticUpdate(n uint64) { pr.Next = n + 1 }

// 根据对应Progress的状态和MsgAppResp消息携带的提示信息，完成Progress.Next的更新
// maybeDecrTo（）方法的两个参数都是MsgAppResp消息携带的信息：
// reject是被拒绝MsgApp消息的Index字段值，
// matchHint是被拒绝MsgAppResp消息的RejectHint字段值（即对应Follower节点raftLog中最后一条Entry记录的索引）
func (pr *Progress) MaybeDecrTo(rejected, matchHint uint64) bool {
	if pr.State == StateReplicate {
		if rejected <= pr.Match {	// 出现过时的MsgAppResp消息，直接忽略
			return false
		}
		// 根据前面对MsgApp消息发送过程的分析，处于StateReplicate状态时，
		// 发送MsgApp消息的同时会直接调用Progress.optimisticUpdate（）方法增加Next，
		// 这就使得Next可能会比Match大很多，这里回退Next至Match位置，并在后面重新发送MsgApp消息进行尝试
		pr.Next = pr.Match + 1
		return true
	}

	if pr.Next-1 != rejected {	// 出现过时的MsgAppResp消息，直接忽略
		return false
	}

	// 根据MsgAppResp携带的信息重直Next
	pr.Next = max(min(rejected, matchHint+1), 1)
	pr.ProbeSent = false
	return true
}

// 检测当前节点是否能够向对应的节点发送消息
func (pr *Progress) IsPaused() bool {
	switch pr.State {
	case StateProbe:	// StateProbe状态时检测ProbeSent字段
		return pr.ProbeSent
	case StateReplicate:	// StateReplicate状态时检测已发送未响应的消息个数
		return pr.Inflights.Full()
	case StateSnapshot:	// StateSnapshot状态时始终可以发送消息
		return true
	default:
		panic("unexpected state")
	}
}

func (pr *Progress) String() string {
	var buf strings.Builder
	fmt.Fprintf(&buf, "%s match=%d next=%d", pr.State, pr.Match, pr.Next)
	if pr.IsLearner {
		fmt.Fprint(&buf, " learner")
	}
	if pr.IsPaused() {
		fmt.Fprint(&buf, " paused")
	}
	if pr.PendingSnapshot > 0 {
		fmt.Fprintf(&buf, " pendingSnap=%d", pr.PendingSnapshot)
	}
	if !pr.RecentActive {
		fmt.Fprintf(&buf, " inactive")
	}
	if n := pr.Inflights.Count(); n > 0 {
		fmt.Fprintf(&buf, " inflight=%d", n)
		if pr.Inflights.Full() {
			fmt.Fprint(&buf, "[full]")
		}
	}
	return buf.String()
}

// ProgressMap是*进度的地图。
type ProgressMap map[uint64]*Progress

// String按排序键顺序打印ProgressMap，每行一个进度。
func (m ProgressMap) String() string {
	ids := make([]uint64, 0, len(m))
	for k := range m {
		ids = append(ids, k)
	}
	sort.Slice(ids, func(i, j int) bool {
		return ids[i] < ids[j]
	})
	var buf strings.Builder
	for _, id := range ids {
		fmt.Fprintf(&buf, "%d: %s\n", id, m[id])
	}
	return buf.String()
}
